This invention relates to the field of electronic communications systems and, more particularly, to interleavers for performing code modulation.
Techniques for encoding communication channels, known as coded modulation, have been found to improve the bit error rate (BER) of electronic communication systems such as modem and wireless communication systems. Turbo coded modulation has proven to be a practical, power-efficient, and bandwidth-efficient modulation method for xe2x80x9crandom-errorxe2x80x9d channels characterized by additive white Gaussian noise (AWGN) or fading. These random-error channels can be found, for example, in the code division multiple access (CDMA) environment.
The key innovation of turbo codes is an interleaver which permutes the original received or transmitted data frame before input to a second encoder. Permuting is accomplished by a processor performing a randomizing algorithm, the construction of which is well known. Combining the permuted data frames with the original data frames has shown to achieve low bit-error rates in AWGN and fading channels. The interleaving process increases the diversity in the data in such a way that if the modulated symbol is distorted in transmission the error may be recoverable with the use of error correcting algorithms in the decoder.
A conventional interleaver collects, or frames, the signal points to be transmitted into a matrix, where the matrix is sequentially filled up a row at a time. After a predefined number of signal points have been framed, the interleaver is emptied by sequentially reading out the columns of the matrix for transmission. As a result, signal points in the same row of the matrix that were near each other in the original signal point flow are separated by a number of signal points equal to the number of rows in the matrix. Ideally, the number of columns and rows would be picked such that interdependent signal points, after transmission, would be separated by more than the expected length of an error burst for the channel. However, this may not be practicable. As the number of rows is increased, so is the signal delay due to the framing of the signal points. As a result, there is a system constraint on the size of the interleaver in order to keep the signal delay within acceptable limits. On the other hand, constraining the size of the interleaver limits the separation of the time-diverse interdependent signal points and thus limits the improvement in error performance achieved by the interleaver.
There are two conventional interleaving methods; uniform interleaving (i.e. a regular interleaving pattern); and non-uniform interleaving (i.e. a pseudo-irregular interleaving pattern). In the case of uniform interleaving, finite code words (FC) of higher weight can be constructed from FCs of lower weight. Therefore a certain xe2x80x9crepetitive patternxe2x80x9d of low-weight FC output sequences can occur in the output stream of a uniform-interleaving turbo coder. However, uniform interleaving does not sufficiently de-correlate the output of the two encoders, hence the minimum distance of the resulting turbo code does not increase as one might expect.
On the other hand, non-uniform interleaving achieves better xe2x80x9cmaximum scatteringxe2x80x9d of data and xe2x80x9cmaximum disorderxe2x80x9d of the output sequence, which means that the redundancy introduced by the two convolutional codes is more equally spread in the output sequence of the turbo encoder. The minimum distance is increased to much higher values than for uniform interleaving. A persistent problem for non-uniform interleaving is how to achieve sufficient xe2x80x9cnon-uniformityxe2x80x9d, since the interleaving algorithms can only be based on pseudo-irregular patterns. Besides this, the effort for implementing the scheme should be reasonable for practical applications. Furthermore, conventional interleavers require a significant amount of memory in the encoder. Conventional interleaving matrices also require delay compensations, which limit their use for applications with real-time requirements.
Accordingly there exists a need for systems and methods of interleaving codes that improve non-uniformity.
There also exists a need for systems and methods of interleaving codes that require minimal delay compensations.
It is thus an object of the present invention to provide systems and methods of interleaving codes that improve non-uniformity.
It is also an object of the present invention to provide systems and methods of interleaving codes that require minimal delay compensations.
In accordance with the teachings of the present invention, these and other objects may be accomplished by the present invention, which interleaves a data frame, where the data frame has a predetermined size and is made up of portions. An embodiment of the invention includes a memory configured to receive and store the data frame. Once received, the data frame is indexed by a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size. The product of the predetermined row size and the predetermined column size equals the predetermined size of the data frame.
A processor is coupled to the memory and used for separating the data frame into a plurality of portions. The processor also is used for generating a permuted sequence of the plurality of portions which are indexed by the plurality of rows in accordance with i1(n1)=xcex11{circumflex over ( )}(n1)mod(P1), where P1 is a prime number greater than the predetermined row size, where n1 is an integer in the range of 1 through and including P1xe2x88x921, and where xcex11 is a root of P1. This algorithm enables i1(n1) to be a unique number between 1 and the predetermined row size.
The processor is also configured to generate a permuted sequence of the plurality of portions indexed by the plurality of columns in accordance with i2(n2)=xcex12{circumflex over ( )}(n2)mod(P2), where P2 is a prime number greater than the predetermined column size, where n2 is an integer in the range of 1 through and including P2xe2x88x921, and where xcex12 is a root of P2. This algorithm enables i2(n2) to be a unique number between 1 and the predetermined column size. The result is interleaved portions of the dataframe.